package com.wang.sort3;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @Author: along
 * @Create: 2021/4/23
 * @Description:图的数据结构实现
 */
public class Demo08_GraphGenerator {
    //点
    public class Node {
        public int value;//节点值
        public int in;//入度
        public int out;//出度
        public ArrayList<Node> nexts;//直接邻居
        public ArrayList<Edge> edges;//边

        public Node(int value) {
            this.value = value;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }
        //边
        public class Edge {
            public int weight;//权重
            public Node from;
            public Node to;

            public Edge(int weight, Node from, Node to) {
                this.weight = weight;
                this.from = from;
                this.to = to;
            }
        }
        //图
        public class Graph {
            public HashMap<Integer, Node> nodes;
            public HashSet<Edge> edges;

            public Graph() {
                this.nodes = new HashMap<>();
                this.edges = new HashSet<>();
            }
        }
        //生成一个图的结构
        public  Graph createGraph(Integer[][] matrix) {
            Graph graph = new Graph();
            for (int i = 0; i < matrix.length; i++) { // matrix[0][0], matrix[0][1]  matrix[0][2]
                Integer from = matrix[i][0];
                Integer to = matrix[i][1];
                Integer weight = matrix[i][2];
                if (!graph.nodes.containsKey(from)) {
                    graph.nodes.put(from, new Node(from));
                }
                if (!graph.nodes.containsKey(to)) {
                    graph.nodes.put(to, new Node(to));
                }
                Node fromNode = graph.nodes.get(from);
                Node toNode = graph.nodes.get(to);
                Edge newEdge = new Edge(weight, fromNode, toNode);
                fromNode.nexts.add(toNode);
                fromNode.out++;
                toNode.in++;
                fromNode.edges.add(newEdge);
                graph.edges.add(newEdge);
            }
            return graph;
        }
}
